package com.leetcode.sorts.arrays.binary_search;

/**
 * @Author: WuPeng
 * @Date: 2021/5/20 4:10 下午
 *
 * 069：x的平方根
 *      实现int sqrt(int x)函数。
 *      计算并返回x的平方根，其中x 是非负整数。
 *      由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
 *
 * 示例 1:
 *      输入: 4
 *      输出: 2
 * 示例 2:
 *      输入: 8
 *      输出: 2
 * 说明:
 *      8 的平方根是 2.82842...,
 *      由于返回类型是整数，小数部分将被舍去。
 *
 */
public class SquareOfX_069 {

    public static int squareOfX(int target){
        int left = 0, right = target, ans = -1;
        while (left <= right){
            int mid = (left + right) >> 1;
            // 转换为long类型，防止mid*mid超出界限
            if ((long)mid * mid <= target){
                ans = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(squareOfX(2147395599));
    }

}
